package xyz.scootaloo.oj.offer

import org.junit.Test

/**
 * @author flutterdash@qq.com
 * @since 2021/4/11 22:27
 */
class P42 {

    private fun maxSubArray(nums: IntArray): Int {
        if (nums.isEmpty()) return 0
        if (nums.size == 1) return nums[0]

        val size = nums.size
        val dp = IntArray(2)
        dp[0] = nums[0]

        var max = nums[0]
        for (idx in 1 until size) {
            dp[1] = Math.max(nums[idx], dp[0] + nums[idx])
            if (dp[1] > max)
                max = dp[1]
            dp[0] = dp[1]
        }

        return max
    }

    @Test
    fun test0() {
        val input = intArrayOf(-2, 1, -3, 4, -1, 2, 1, -5, 4)
        println(maxSubArray(input))
    }

}
